/**
* 
**/
#include <stdio.h>
#include <stdlib.h>

// 递归
int fibonacci0(int n)
{
  return n < 2 ? 1 : (fibonacci0(n-1) + fibonacci0(n-2));
}

// 递推,得到一个解,只能得到一个解
int fibonacci1(int n)
{
  if (n < 2) {
    return 1;
  }
  
  int sum=0,f0=1,f1=1;
  while (--n) { // 循环n-1次即可
    sum = f0 + f1;
    f0  = f1;
    f1  = sum;
  }
  return sum;
}

// 递推,求出所有解,占用过多空间
int *fibonacci2(int n)
{
  int *result = (int*)malloc(sizeof(int) * n);
  if (NULL == result) {
    exit(-1);
  }
  
  int i = 0;
  *(result + i++) = 1; // i=0
  *(result + i++) = 1; // i=1
  
  for (;i < n; ++i) {
    *(result + i)  = *(result + i - 1) + *(result + i - 2);
  }
  return result;
}

int main(int argc, char *argv[])
{
  int i, n = 20;
  for (i=0;i<n;++i){
    printf("%d,", fibonacci0(i));
  }
  printf("\n");

  for (i=0;i<n;++i){
    printf("%d,", fibonacci1(i));
  }
  printf("\n");
  
  int *f = fibonacci2(n); // 一次性得到多个解
  for (i=0;i<n;++i){
    printf("%d,", *(f+i));
  }
  printf("\n");
  
  return 0;
}
